//记忆化搜索，将小数已经成立的在大数中不再考虑，从上次结束地点继续访问
class Solution {
public:
    using PII=pair<int, int>;
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        vector<PII> spellsPos(spells.size());
        vector<int> ans(spells.size(), 0);
        for(int i=0; i<spells.size(); i++)
            spellsPos.push_back({spells[i], i});
        
        sort(spellsPos.begin(), spellsPos.end());
        sort(potions.begin(), potions.end());
        //倒着访问potions
        int en=potions.size()-1; //en是不成立的右端点
        for(auto &[spell, pos]:spellsPos)
        {
            while(en>=0&&1ll*potions[en]*spell>=success) en--;
            ans[pos]=potions.size()-en-1;
        }
        return ans;
    }
};